The present invention relates to a shaping method to convert an incoming data flow with an incoming data packet rate into an outgoing data flow with an outgoing data packet rate, to a shaper realizing such a shaping method and a communication network including such a shaper.
As described in the ATM Forum, Technical committee xe2x80x9cTraffic Management Specificationxe2x80x9d Version 4.0 ATM Forum/95-0013R10, February 1996, at section 5.5 Traffic Shaping, page 41, traffic shaping is a mechanism that alters the traffic characteristics of a stream of cells on a connection to achieve better network efficiency whilst meeting the Quality Of Service objectives, or to ensure conformance at a subsequent interface. Traffic shaping maintains cell sequence integrity on a connection. Examples of traffic shaping are e.g., mean cell rate reduction, burst length limiting, reduction of Cell Delay Variation by suitable spacing cells in time and cell scheduling policy.
Shaping methods have also been proposed to reduce the burstiness of video traffic. Indeed, a shaping method realized by a shaper being included in a communication network is already known in the art, e.g., from the article xe2x80x9cAdaptive traffic smoothing for live VBR MPEG video servicexe2x80x9d written by Jin-soo Kim and Jae-kyoon Kim and published in Computer Communications 21 (1998) pages 644-653 by Elsevier Science B. V.
Therein, an on-line source traffic smoothing method is proposed that can be effectively used in live video applications such as visual lectures or television news. Through experimental results, it is shown that the proposed scheme, which is designed in such a dynamic way as to smooth maximally the transmission rate, is effective in reducing the peak rate, temporal variations, and effective bandwidth of a given video stream. According to the system model that is described in section 2 of this article, the method converts an incoming data flow with an incoming data packet rate into an outgoing data flow with an outgoing data packet rate. Indeed, the system model includes a buffer, called in the article the sender buffer, wherein the received data packets of the incoming data flow transmitted by the source are buffered. The buffered data packets are leaked with a transmission rate, called hereafter outgoing data packet rate, whereby an outgoing data flow is provided.
In section 3 of the above article it is mentioned that the video smoothing method of the above mentioned article depends on the past information of the outgoing data packet rate as well as the buffer occupancy of the buffer. Furthermore, the system model, called hereafter shaper, includes a Lth order linear predictor in order to efficiently estimate a future incoming data packet rate by using a linear combination of the previous values of the incoming data packet rate.
In this way, the shaping method of the prior art document includes among others the steps of:
determining a value of a future incoming data packet rate of the incoming data packet rate; and
determining a value of a buffer occupancy related to the number of data packets of the incoming data flow which are received and are buffered by the buffer; and the step of
determining a value of an outgoing data packet rate in function of among others a value of the future incoming data packet rate and a value of the buffer occupancy.
As it is described in the article, the video smoothing method supports Variable bit Rate VBR MPEG video services.
However, a quality of service category that provides a service with a predetermined minimum guaranteed bandwidth according to a predetermined minimum data packet rate of an incoming data flow and which allows use of excess bandwidth, being limited according to a predetermined peak data packet rate, over this predetermined minimum guaranteed bandwidth, is not supported by the prior art method. Such a service category is e.g., the Guaranteed Frame Rate GFR service category. This service category provides a service with a minimum guaranteed bandwidth while allowing the users to transmit at a higher rate than this guaranteed bandwidth. The data packets that are part of the minimum guaranteed bandwidth will be delivered to the destination while the data packets which are not part of this guaranteed bandwidth will be delivered to the destination on a best-effort basis depending on the amount of the unreserved bandwidth inside the network. A traffic contract for such a GFR service includes the definition of a Minimum Cell Rate MCR and a Peak Cell Rate for each data flow. Such a minimum cell rate MCR, called hereafter minimum data packet rate, is expressed in cells per second. The minimum guaranteed bandwidth according to this minimum data packet rate is the minimum bandwidth that is guaranteed at any time for each established data flow following the contract and is determined during connection set-up of the data flow. Such a peak cell rate, called hereafter peak data packet rate, is the maximum transmission rate that is allowed according to the contract.
An object of the present invention is to provide a shaping method and a shaper realizing such a shaping method in a communication network that does not reduce the burstiness of the incoming data packet rate of the incoming data flow while supporting a quality of service category which provides a service with a predetermined minimum guaranteed bandwidth according to a predetermined minimum data packet rate of an incoming data flow and which allows use of excess bandwidth, being limited according to a predetermined peak data packet rate, over this predetermined minimum guaranteed bandwidth.
Indeed, due to the fact that the shaping method further includes determining the value of the outgoing data packet rate also in function of a predetermined peak data packet rate and a predetermined minimum data packet rate. In this way, the minimum data packet rate according to the contract of the incoming data flow is taken into account in order to determine a value for the outgoing data packet rate whereby the shaping method is enabled to guarantee a minimum guaranteed bandwidth according for the data flow. Moreover, the shaper is enabled to allow the use of excess bandwidth over the minimum guaranteed bandwidth if this bandwidth is available in the network and to limit the use of excess bandwidth, however, according to the predetermined peak data packet rate.
It has to be remarked that the minimum data packet rate is, as already mentioned above, a data packet rate that is guaranteed to the incoming data flow. This does not mean that the minimum value of incoming data packet rates of the incoming data flow is equal to this minimum data packet rate. Indeed, the incoming data packet rate might be smaller than this minimum data packet rate but the minimum data packet rate is always guaranteed to this incoming data flow.
A possible implementation of the step of determining a value of a future incoming data packet rate is to determine a value of an average incoming data packet rate of the incoming data packet rate.
A simple solution in order to reduce the burstiness of the incoming data packet rate is to use the above mentioned value of an average incoming data packet rate in order to determine a value for the outgoing data packet rate. Although this solution would limit the burstiness of the incoming data packet rate, it would result in a large and uncontrolled occupancy of the buffer included in the shaper. Therefore two thresholds are predetermined on the occupancy of the buffer: a predetermined minimum buffer occupancy and a predetermined maximum buffer occupancy.
As long as the value of the buffer occupancy is smaller than the predetermined minimum buffer occupancy or substantially equal to the predetermined minimum buffer occupancy, the shaper is allowed to leak the buffer with an outgoing data packet rate which is at least equal to the guaranteed minimum data packet rate. However, in the event when a bigger incoming data packet rate is expected, i.e., a bigger value of the future incoming data packet rate is determined, the buffer should be leaked according to this future incoming data packet rate. In this way, in the event when a value of the buffer occupancy is smaller than or equal to the predetermined minimum buffer occupancy, the shaping method further determines the value of the outgoing data packet rate with the maximum out of the predetermined minimum data packet rate or the future incoming data packet rate.
Furthermore, in the event when the buffer occupancy is between the predetermined minimum buffer occupancy and the predetermined maximum buffer occupancy the shaping method further determines the value of the outgoing data packet rate with a function which is directly proportional to the value of the buffer occupancy and which is bounded between the minimum data packet rate and the peak data packet rate. Indeed, in order to keep the buffer occupancy under control, the higher the buffer occupancy becomes, the higher the outgoing data packet rate will be.
In the event when the buffer occupancy is equal to or bigger than the predetermined maximum buffer occupancy the shaping method further determines the value of the outgoing data packet rate with the predetermined peak data packet rate which is also predefined in the above mentioned traffic contract during connection set-up of the data flow and which is the maximum data packet rate with which the source of the data flow is allowed to transmit data packets. In order to avoid loss of data packets in the buffer, and in the event when the buffer occupancy is already equal or higher as the predefined maximum buffer occupancy, the shaper can not effort itself to leak the buffer at a too small outgoing data packet rate, whereby it is necessary to leak the buffer with an outgoing data packet rate equal to this predetermined peak data packet rate.
A further characteristic feature of the present invention is that, in the event when the value of the buffer occupancy is between the predetermined minimum buffer occupancy and the predetermined maximum buffer occupancy, the outgoing data packet rate is the maximum of
a value of the future incoming data packet rate; and
a linear function a value of this buffer occupancy with a slope which is equal to a fraction of the difference between the predetermined peak data packet rate and the predetermined minimum data packet rate, over the difference between the predetermined maximum buffer occupancy and the predetermined minimum buffer occupancy.
Indeed, different kinds of curves are possible to implement the function in order to be proportional to the buffer occupancy. Furthermore, as long as the value of the future incoming data packet rate is bigger than the value of the function of the buffer occupancy, the buffer will be leaked at this future incoming data packet rate.
However, according to the above paragraph, the buffer will be relieved, i.e., the outgoing data packet rate will increase, only at the point when the average incoming data packet rate and the result of the linear function are crossing each other. This means that the point of relieving the buffer depends on the incoming traffic and not directly on the predetermined minimum buffer occupancy. Therefore a further improvement is provided to the shaper. In the event the value of the buffer occupancy is between a predetermined minimum buffer occupancy and a predetermined maximum buffer occupancy the outgoing data packet rate is determined with a linear function with an interception at a maximum out of the predetermined minimum data packet rate and the average incoming data packet rate and with a slope which is substantially equal to a fraction of the difference between the predetermined peak data packet rate and a maximum out of the predetermined minimum data packet rate and the future incoming data packet rate, over the difference between the predetermined maximum buffer occupancy and the predetermined minimum buffer occupancy. In this way, once the value of the predetermined minimum buffer occupancy is reached, the buffer will be leaked with an increasing outgoing data packet rate.
A further characteristic feature of the present invention is that the step of determining a value of a future incoming data packet rate is realized for different group data packet rates whereby the step of determining a value of the outgoing data packet rate is executed by using these different group data packet rates according to different kind of situations. Indeed, in the event when the incoming data packets of the incoming data flow are each part of one of a plurality of predefined group data packets, a future group data packet rate is determined for each group of data packets. The step of determining a value of the outgoing data packet rate in function of a value of the future incoming data packet rate is realized by constituting this future incoming data packet rate by a value of one of the group data packet rates. A possible way to implement the condition of when to use which value of a group data packet rate is, e.g., according to a predefined sequence among the different predefined groups. A second way to implement this condition is e.g. according to the group data packet whereto an outgoing data packet of the outgoing data flow belongs to. A possible way to predefine different group data packets is according to its Cell Loss Priority bit, called hereafter CLP bit, which is included in each Asynchronous Transfer Mode data packet, called ATM cell. In this way, two predefined group of data packets are defined: a first group of ATM cells included in the incoming ATM data flow are the ATM cells having a CLP bit equal to 1 and a second group of ATM cells included in the incoming ATM data flow are the ATM cells having a CLP bit equal to 0. During receiving of the incoming ATM data flow, two future incoming data packet rates are maintained, a first future group data packet rate which is which is associated to the first group and which is based on the total amount of incoming data packets and a second future group data packet rate which is associated to the second group and which is only based on the ATM cells included in the second group of data packets i.e. CLP bit=0. After being buffered, an incoming ATM cell of the incoming data flow is going to be transmitted at an outgoing data packet rate. In the event when the outgoing data packet includes a CLP bit equal to 1, i.e., it belongs to the first group of data packets, the future incoming data packet rate which is used during execution of the step of determining the outgoing data packet rate is constituted by the first future group data packet rate. In the event when the outgoing data packet includes a CLP bit equal to 0, i.e., it belongs to the second group of data packets, the future incoming data packet rate which is used during execution of the step of determining the outgoing data packet rate is constituted by the second future group data packet rate.
Similar to using different kinds of future group data packet rates for different kinds of groups in order to determine the outgoing data packet rate, also any one of the buffer occupancy, the predefined maximum buffer occupancy and the predefined minimum buffer occupancy can be maintained for the different groups in order to determine the outgoing data packet rate for the outgoing data packets. In this way any one of a value of a group buffer occupancy, i.e., a predefined maximum buffer occupancy of a group, a value of a group predetermined maximum buffer occupancy, i.e., a predetermined maximum buffer occupancy of a group, and a value of a group predetermined minimum buffer occupancy, i.e., a predetermined minimum buffer occupancy of a group, are defined and maintained for one of the plurality of groups. Furthermore, in the event when an outgoing data packet of an outgoing data flow is included in a first group data packet of a plurality of group data packets, the outgoing data packet rate is determined in function of any one of:
a value of a first future group data packet rate;
a value of a first group buffer occupancy;
a value of a first group predetermined maximum buffer occupancy;
a value of a first group predetermined minimum buffer occupancy.
Furthermore, in the event when such a group parameter is used in order to determine the outgoing data packet rate for a data packet which belongs to a certain group, the outgoing data packet rate for a data packet which belongs to another group is not necessarily be determined by using such group parameters. Indeed, according to the above described example of CLP=1 and CLP=0, the outgoing data packet rate of the group CLP=1 can be put to a constant outgoing data packet rate which is equal to the predetermined peak data packet rate. In this way, for the group CLP=1, a faster outgoing data packet rate is determined whereby the ATM cells of this group are faster transmitted into the network and might be discarded later on in the network. However, for the group CLP=0, a slower outgoing data packet rate is determined whereby the ATM cells of this group are slower transmitted into the network and are better protected by the system.
It should be noticed that the term xe2x80x9cincludingxe2x80x9d, used in the claims, should not be interpreted as being limited to the means listed thereafter. Thus, the scope of the expression xe2x80x9ca device including means A and Bxe2x80x9d should not be limited to devices consisting only of components A and B. It means that with respect to the present invention, the only relevant components of the device are A and B.
Similarly, it is to be noted that the term xe2x80x9ccoupledxe2x80x9d, also used in the claims, should not be interpreted as being limited to direct connections only. Thus, the scope of the expression xe2x80x9ca device A coupled to a device Bxe2x80x9d should not be limited to devices or systems wherein an output of device A is directly connected to an input of device B. It means that there exists a path between an output of A and in input of B which may be a path including other devices or means.